import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Demo8 {

    int m,n;
    int[] dx={0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int[][] memo;
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;

        memo = new int[m][n];

        int ret = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                ret = Math.max(ret, dfs(matrix,i,j));
            }
        }
        return ret;



    }

    private int dfs(int[][] matrix, int i, int j) {

        if (memo[i][j] != 0){
            return memo[i][j];
        }
        int ret = 1;
        for(int k  =0;k<4;k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if (x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]){
                ret = Math.max(ret, dfs(matrix,x, y)+1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }








/*    int[][] memo;
    public int getMoneyAmount(int n) {

        memo = new int[n+1][n+1];
        return dfs(1,n);
    }

    private int dfs(int left, int right) {



        if (left>=right) return 0;

        if (memo[left][right]!=0){
            return memo[left][right];
        }

        int ret = Integer.MAX_VALUE;
        for(int head = left;head <= right; head++){
            int x = dfs(left,head-1);
            int y = dfs(head+1,right);
            ret = Math.min(ret,Math.max(x,y)+head);
        }
        memo[left][right] = ret;


        return ret;




    }*/







    /*public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int ret = 0;
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if (nums[j]>nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]);
                }
            }
            ret = Math.max(ret,dp[i]);
        }

        return ret;


    }*/

/*    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        int n = nums.length;
        int[] memo = new int[n];

        for(int i = 0;i<n;i++){
            ret = Math.max(ret,dfs(i,nums,memo));
        }
        return ret;
    }*/


   /* private int dfs(int pos, int[] nums,int[] memo) {
        if (memo[pos]!=0){
            return memo[pos];
        }
        int ret = 1;
        for(int i = pos+1;i<nums.length;i++){
            if (nums[i] > nums[pos]){
                ret = Math.max(ret,dfs(i,nums,memo)+1);
            }
        }
        memo[pos] = ret;
        return ret;

    }*/




/*    public int uniquePaths(int m, int n) {

        int[][] dp = new int[m+1][n+1];
        dp[1][1]=1;
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if (i==1 && j==1){
                    continue;
                }
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];


    }*/

   /* private int dfs(int i, int j,int[][] memo) {

        if (memo[i][j] != 0){
            return memo[i][j];
        }

        if (i==0 || j==0){
            return 0;
        }
        if (i==1 && j==1)
        {
            memo[i][j] = 1;
            return 1;
        }
        memo[i][j] = dfs(i-1,j,memo)+dfs(i,j-1,memo)
        return memo[i][j];

    }*/



/*    public int uniquePaths(int m, int n) {

        int[][] memo = new int[m+1][n+1];

        return dfs(m,n,memo);
    }

    private int dfs(int i, int j,int[][] memo) {

        if (memo[i][j] != 0){
            return memo[i][j];
        }

        if (i==0 || j==0){
            return 0;
        }
        if (i==1 && j==1)
        {
            memo[i][j] = 1;
            return 1;
        }
        memo[i][j] = dfs(i-1,j,memo)+dfs(i,j-1,memo);
        return memo[i][j];

    }*/




/*    int[] dp;
    public int fib(int n) {
        dp = new int[31];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];

    }*/


/*    int[] memo;

    public int fib(int n) {

        memo = new int[31];
        return dfs(n);
    }

    private int dfs(int n) {
        if (memo[n] != 0){
            return memo[n];
        }

        if (n==0 || n==1){
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n - 1) + dfs(n-2);
        return memo[n];
    }*/







    /*int[] dx = {0,1};
    int[] dy = {1,0};
    int m,n;
    int[][] vis;
    int count;
    public int wardrobeFinishing(int _m, int _n, int cnt) {
        m = _m;
        n = _n;
        vis = new int[m][n];

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                dfs(i,j,cnt);
            }
        }

        return count;

    }

    private void dfs(int i, int j, int cnt) {
        vis[i][j]=1;
        count++;

        for(int k = 0;k<2;k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if (x>=0&&x<m&&y>=0&&y<n&&vis[i][j]==0&&fun(x,y)<=cnt){
                dfs(x,y,cnt);
            }
        }


    }

    private int fun(int x, int y) {
        int a=0,b=0;
        while (x>0){
            a =a+ x%10;
            x/=10;
        }
        while (y>0){
            b = b+y%10;
            y/=10;
        }
        return a+b;
    }
*/


/*    int[] dx = {0,0,1,-1,1,1,-1,-1};
    int[] dy = {1,-1,0,0,1,-1,1,-1};
    int m,n;
    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;
        n = board[0].length;

        int x = click[0],y=click[1];
        if(board[x][y]=='M'){
            board[x][y] = 'X';
            return board;
        }
        dfs(board,x,y);

        return board;

    }

    private void dfs(char[][] board, int i, int j) {
        int count = 0;
        for(int k = 0;k<8;k++){
            int x = dx[k] + i;
            int y = dy[k] + j;
            if (x>=0 && x<m && y>=0&&y<n && board[x][y] == 'M'){
                count++;
            }
        }

        if (count==0){
            board[i][j]='B';
            for(int k = 0;k<8;k++){
                int x = dx[k] + i;
                int y = dy[k] + j;
                if (x>=0 && x<m && y>=0&&y<n && board[x][y] == 'E'){
                    dfs(board, x, y);
                }
            }
        }else{
            board[i][j] = (char)(count+'0');
            return;
        }



    }*/




    /*int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int m,n;
    int[][] vis;
    List<List<Integer>> ret;

    public List<List<Integer>> pacificAtlantic(int[][] nums) {
        m = nums.length;
        n = nums[0].length;
        vis = new int[m][n];

        for(int i=0;i<n;i++){
            dfs(nums,0,i);
            dfs(nums,m-1,i);
        }

        for(int i=0;i<n;i++){
            dfs(nums,i,0);
            dfs(nums,i,n-1);
        }
        List<Integer> path = new ArrayList<>();
        for(int i =0;i<m;i++){
            for(int j=0;j<n;j++){
                if (vis[i][j]==2){
                    path.add(i);
                    path.add(j);
                    ret.add(new ArrayList<>(path));
                }
            }
        }

        return ret;


    }

    private void dfs(int[][] nums, int i, int j) {
        vis[i][j]++;

        for(int k = 0;k<4;k++){
            int x = i+dx[k];
            int y = j + dy[k];
            if (x>=0&&x<m && y>=0&&y<n && vis[x][y]==0 && nums[x][y]>=nums[i][j]){
                dfs(nums,x,y);
            }
        }

    }
*/







   /* int m,n;
    int[][] vis;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        vis = new int[m][n];

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if (i==0 || j==0 || i==m-1 || j==n-1){
                    if (board[i][j] == 'O' && vis[i][j]==0)
                        dfs(board, i, j, '.');
                }
            }
        }

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if (board[i][j]=='.'){
                    board[i][j]='O';
                } else if (board[i][j]=='O'){
                    board[i][j] ='X';
                }

            }
        }




    }

    private void dfs(char[][] board, int i, int j ,char c) {
        vis[i][j]=1;
        board[i][j]=c;

        for(int k = 0;k<4;k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if (x>=0&&x<m&&y>=0&&y<n&&vis[x][y]==0&&board[x][y]=='O'){
                dfs(board,x,y,c);
            }
        }


    }
*/

   /* int m,n;
    int[][] vis;
    int max;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int count = 0;
    public int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        max = 0;
        vis = new int[m][n];


        for(int i = 0 ;i<m;i++){
            for(int j=0;j<n;j++){
                count=0;
                if (vis[i][j] == 0 && grid[i][j] == 1 ){
                    dfs(grid,i,j);
                    max = Math.max(max,count);
                }
            }
        }
        return max;
    }

    private void dfs(int[][] grid, int i, int j) {
        vis[i][j]=1;
        count++;
        for(int k = 0;k<4;k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if (x>=0&&x<m&&y>=0&&y<n&&vis[x][y]==0&&grid[x][y]==1){
                dfs(grid,x,y);
            }
        }


    }*/





/*
    int m,n;
    int count;
    int[][] vis;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int numIslands(char[][] grid) {
        m=grid.length;
        n=grid[0].length;
        vis= new int[m][n];

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if (vis[i][j]==0 && grid[i][j]=='1'){

                    dfs(grid,i,j);
                    count++;

                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {

        vis[i][j]=1;

        for(int k = 0; k<4; k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if (x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&vis[x][y]==0){
                dfs(grid,x,y);
            }

        }



    }
*/



/*

    int m,n;
    int count;
    public int numIslands(char[][] grid) {
        m=grid.length;
        n=grid[0].length;
        char[][] num = new char[m+1][n+1];

        for(int i=0;i<m+1;i++){
            for(int j =0;j<n+1;j++){
                if (i!=0 && i!=m-1 && j!=0 && j!=n-1){
                    num[i][j] = grid[i-1][j-1];
                }
                num[i][j]='0';
            }
        }


        for(int i = 1;i<m-1;i++){
            for(int j = 1;j<n-1;j++){
                //判断上下左右是不是1
                if (num[i][j] == '1' && num[i-1][j]=='0' && num[i][j-1]=='0') {
                    count++;
                }
            }
        }
        return count;
    }
*/


    /*int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int m,n;
    int prev;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc]==color)return image;
        m = image.length;
        n = image[0].length;
        dfs(image,sr,sc,color);

        return image;
    }

    private void dfs(int[][] image, int i, int j, int color) {
        prev = image[i][j];
        image[i][j] = color;

        for(int k=0;k<4;k++){
            int x = i+dx[k];
            int y = j +dy[k];
            if (x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev){
                dfs(image, x, y, color);
            }
        }
    }
*/

}
